package 二叉树;

import java.util.ArrayList;
import java.util.List;

public class No257二叉树的所有路径 {

    /**
     * 给定一个二叉树，返回所有从根节点到叶子节点的路径。
     *
     * 说明: 叶子节点是指没有子节点的节点。
     *
     * 示例:
     *
     * 输入:
     *
     *    1
     *  /   \
     * 2     3
     *  \
     *   5
     *
     * 输出: ["1->2->5", "1->3"]
     *
     * 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
     */

    private List<String> list=new ArrayList<>();

    public List<String> binaryTreePaths(TreeNode root) {

        dg(root,null);

        return list;
    }

    //这样比较慢,再写一个递归传值的方法
    private void dg(TreeNode node,String str){
        if(node==null)
            return;
        StringBuilder stringBuilder=new StringBuilder(str);
        if(node.left==null&&node.right==null){
            stringBuilder.append(node.val);
            list.add(stringBuilder.toString());
            return;
        }
        stringBuilder.append(node.val).append("->");
        dg(node.left,stringBuilder.toString());
        dg(node.right,stringBuilder.toString());
    }

}
